#include <bits/stdc++.h>

using namespace std;

/*
2040. 两个有序数组的第 K 小乘积
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
 

示例 1：

输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8
解释：第 2 小的乘积计算如下：
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘积为 8 。
示例 2：

输入：nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出：0
解释：第 6 小的乘积计算如下：
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
第 6 小的乘积为 0 。
示例 3：

输入：nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出：-6
解释：第 3 小的乘积计算如下：
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
第 3 小的乘积为 -6 。
 

提示：

1 <= nums1.length, nums2.length <= 5 * 104
-105 <= nums1[i], nums2[j] <= 105
1 <= k <= nums1.length * nums2.length
nums1 和 nums2 都是从小到大排好序的。
*/

// 法一
class Solution {
public:
    // 辅助函数：计算nums2中满足 nums2[j] * x1 <= v 的元素数量（x1正负分开处理）
    int countLessEqual(vector<int>& nums2, long long x1, long long v) {
        int n2 = nums2.size();
        int left = 0, right = n2 - 1;
        
        // 二分查找边界调整
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止整数溢出
            long long product = nums2[mid] * x1;  // 显式计算乘积
            
            // 根据x1的正负调整比较逻辑
            if ((x1 >= 0 && product <= v) || (x1 < 0 && product > v)) {
                left = mid + 1;  // 满足条件时向右扩展
            } else {
                right = mid - 1; // 不满足时向左收缩
            }
        }
        
        // 返回满足条件的数量（x1正负处理方向相反）
        return (x1 >= 0) ? left : (n2 - left);
    }

    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        int n1 = nums1.size();
        // 动态计算初始二分边界（避免固定值1e10可能不够的情况）
        long long left = min({
            (long long)nums1[0] * nums2[0],
            (long long)nums1[0] * nums2.back(),
            (long long)nums1.back() * nums2[0],
            (long long)nums1.back() * nums2.back()
        });
        long long right = max({
            (long long)nums1[0] * nums2[0],
            (long long)nums1[0] * nums2.back(),
            (long long)nums1.back() * nums2[0],
            (long long)nums1.back() * nums2.back()
        });

        // 二分查找第k小的乘积
        while (left <= right) {
            long long mid = left + (right - left) / 2;  // 防止溢出
            long long count = 0;
            
            // 统计所有满足 nums1[i]*nums2[j] <= mid 的组合数
            for (int i = 0; i < n1; i++) {
                count += countLessEqual(nums2, nums1[i], mid);
                // 提前终止：当count超过k时无需继续计算
                if (count > k) break;
            }
            
            // 调整搜索范围
            if (count < k) {
                left = mid + 1;  // 第k小在右半区
            } else {
                right = mid - 1; // 第k小在左半区
            }
        }
        return left;
    }
};

// 法二
class Solution {
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        // 预处理：将nums1和nums2分别划分为负数部分(n)、零部分(z)、正数部分(p)
        const vector<int> n1(begin(nums1), ranges::lower_bound(nums1, 0)),  // nums1的负数部分
                    p1(ranges::upper_bound(nums1, 0), end(nums1)),          // nums1的正数部分
                    n2(begin(nums2), ranges::lower_bound(nums2, 0)),        // nums2的负数部分
                    p2(ranges::upper_bound(nums2, 0), end(nums2));          // nums2的正数部分
        const int z1 = nums1.size() - n1.size() - p1.size(),  // nums1中零的个数
                  z2 = nums2.size() - n2.size() - p2.size();  // nums2中零的个数

        // 辅助函数：计算乘积 <= x 的元素对数
        auto solve = [&](long long x) -> long long {
            long long res = 0;

            // 情况1：处理负数与正数组合的乘积（n1*p2 和 n2*p1）
            if (x >= -1) {
                // 所有n1*p2和n2*p1的组合都 <= x（因为负数*正数 <= -1 <= x）
                res += n1.size() * p2.size() + n2.size() * p1.size();
            } else {
                // 需要精确计算满足 n1[i]*p2[j] <= x 的对数（双指针法）
                for (size_t i = 0, j = 0; i < n1.size() && j < p2.size(); i++) {
                    while (j < p2.size() && 1LL * n1[i] * p2[j] > x) j++;
                    res += p2.size() - j;
                }
                // 同理计算 n2[i]*p1[j] <= x 的对数
                for (size_t i = 0, j = 0; i < n2.size() && j < p1.size(); i++) {
                    while (j < p1.size() && 1LL * n2[i] * p1[j] > x) j++;
                    res += p1.size() - j;
                }
            }

            // 情况2：处理包含零的乘积
            if (x >= 0) {
                // 零与任何数的乘积 <= 0 <= x
                res += z1 * nums2.size() + z2 * nums1.size() - 1LL * z1 * z2;  // 减去重复计算的零与零的组合
            }

            // 如果x <= 0，不需要处理正数*正数和负数*负数的情况（它们的乘积 > 0 > x）
            if (x <= 0) return res;

            // 情况3：处理正数*正数的乘积（p1*p2）
            for (size_t i = 0, j = p2.size(); i < p1.size() && j > 0; i++) {
                while (j > 0 && 1LL * p1[i] * p2[j - 1] > x) j--;
                res += j;
            }

            // 情况4：处理负数*负数的乘积（n1*n2）
            for (size_t i = 0, j = 0; i < n1.size(); i++) {
                // 利用n1和n2都是有序的特性，从后往前匹配
                while (j < n2.size() && 1LL * n1[i] * n2[n2.size() - j - 1] <= x) j++;
                res += j;
                // 优化：如果j已经达到最大值，可以直接计算剩余组合
                if (j == n2.size()) {
                    res += j * (n1.size() - i - 1);
                    break;
                }
            }

            return res;
        };

        // 确定二分搜索的初始范围 [l, r]
        long long l = LLONG_MAX, r = LLONG_MIN;
        // 计算所有可能的极值组合
        if (!n1.empty() && !p2.empty()) {
            l = min(l, 1LL * n1.front() * p2.back());  // 最小负值
            r = max(r, 1LL * n1.back() * p2.front());  // 最大负值
        }
        if (!p1.empty() && !n2.empty()) {
            l = min(l, 1LL * p1.back() * n2.front());  // 最小负值
            r = max(r, 1LL * p1.front() * n2.back());  // 最大负值
        }
        if (!n1.empty() && !n2.empty()) {
            l = min(l, 1LL * n1.back() * n2.back());   // 最小正值
            r = max(r, 1LL * n1.front() * n2.front()); // 最大正值
        }
        if (!p1.empty() && !p2.empty()) {
            l = min(l, 1LL * p1.front() * p2.front()); // 最小正值
            r = max(r, 1LL * p1.back() * p2.back());   // 最大正值
        }
        // 如果存在零，确保范围包含零
        if (z1 + z2 != 0) {
            l = min(l, 0LL);
            r = max(r, 0LL);
        }

        // 二分查找第k小的乘积
        long long res = LLONG_MIN;
        while (l <= r) {
            long long mid = l + (r - l) / 2;  // 防止溢出
            if (solve(mid) >= k) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
};
